14.6 メモリ中心のテクニック
注: p355のサブセクションとしてプロセッサ中心のテクニックとあるが、p350のサブセクションにも同じことが書いてあるので、p355の方はおそらくメモリ中心のテクニックの誤り
スレッド毎のfrom空間とto空間
コピーGCを並列化する単純な設計
コピーGCはオブジェクトの場所に基づいた仕事の分割に適する
コレクタ毎にfrom空間とto空間をもったCheney方式(cf. p57)でやる
Cheney方式
scanポインタとfreeポインタを用いてto空間中に灰色オブジェクトを入れるキューを表現することでワークリストを使わずに済ませる
スレッド毎に独立に連続するメモリチャンクを走査する
問題点
他スレッドとの競争は避けられない
オブジェクトのコピー
mutableオブジェクトの複製を防ぐための競争
転送ポインタの書き込み
負荷分散の性能が悪い
仕事やto空間の空きを分け合う仕組みがない
ブロック構造のヒープ
すぐ思いつく解決策その1
to空間を過剰に分割
ブロックの獲得をめぐってスレッド同士に競争させる
走査対象のブロック
コピー先を割り付けるブロック
Imai and Tick$ [1993]
ヒープを固定長のチャンクに分割
スレッド毎に走査対象とコピー先のチャンクをもたせる
Cheney方式でコピーするのでワークリストは使わない
コピー先のチャンクがいっぱいになるとグローバルプールへ移動させる
次の空のコピー先はフリーチャンクのマネージャからもらう
仕事がなくなったらグローバルプールから走査対象をもってくる
2つの負荷分散機構
チャンク(曰く「ヒープ拡張ユニット」)を小さくする
たった256ワード
問題点: フラグメンテーション
平均してオブジェクトサイズの半分の空間がすべてのチャンクの末尾で無駄になる
約$ 1/2\times(\text{オブジェクトサイズ})\times(\text{チャンク数}) の無駄
解決策: big bag of pages (cf. p111)
オブジェクトサイズが小さいときは、チャンクをそのオブジェクトサイズで等分して、残りの領域を今度同じサイズのオブジェクトが来たときに使う
スレッド毎にコピー先としてN個のチャンクをもつ
おそらくNは小さいオブジェクトサイズの種類数
大きなオブジェクトとチャンクは共有のヒープから割り付け
ロックで管理
チャンクをブロック(曰く「負荷分散ユニット」)に分割する
32ワード程度
小さいほど高速化が期待できる
走査を適宜諦めて次の走査へ着手する
scanポインタを進めたときに、ブロック境界に到達した場合
以下で言う次の走査対象のオブジェクトとは、scanポインタが指すオブジェクトのスロットが参照するfrom空間のオブジェクトのこと？
次の走査対象のオブジェクトの大きさがブロックサイズより小さい以下？の場合(図14-5)
末端の(freeポインタがある)ブロックの先頭までscanポインタを進める
scanポインタが飛ばした範囲(灰色で埋まったブロック)をグローバルプールへ返す
次の走査対象のブロックは競争なしに取得できて、グローバルな競争を減らせる
灰色オブジェクトのコピー先として取得したときに競争済みという意味？
今後走査が必要な灰色のオブジェクトが、コピー先になっているブロックにしか存在しないという状況を避けることもできる。
いまいちよくわからんけど、負荷分散できるということを言いたいのかな？
次の走査対象のオブジェクトの大きさがブロックサイズより大きいがチャンクサイズ以下の場合
scanポインタをコピー先チャンクの先頭に移す
この場合、ブロックのときには省略出来ていた次の走査対象チャンクの取得競争は必要そう
なので、利点は負荷分散だけ？
飛ばした範囲のブロックも同様にグローバルプールへ返すのかな？
次の走査対象のオブジェクトの大きさがチャンクサイズより大きい場合
そのまま走査し、コピーしたオブジェクトはグローバルプールに加える
図14-6: ブロックの遷移図
ブロックの状態によって所属が決まっている
freelist, scanlist, done
グローバルプール中にある
それ以外の状態
いずれかのスレッドのローカルブロック
状態遷移するブロックの色が決まっている
遷移する可能性があるタイミング
scanポインタが走査対象のブロックの終端に到達したとき
copyポインタ(初出！)がコピー先ブロックの終端に到達したとき
scanポインタがフリーfreeポインタに追いついたとき
aliased状態: 走査対象とコピー先が同じ
aliasedブロックのscanは極力しない
aliasedブロックの余白は他の灰色ブロックの追跡によってコピーしてきたオブジェクトで埋める
最後の方で、黒色が入ったaliasedブロックならscanする
表14-1: コピー先、走査対象の色ごとの状態遷移
GHCにおける観測と改善 (Marlow et al.$ [2008] )
ブロックを一度に処理する？ときは、仕事が少ないと逐次処理が多くなる
ちょっと意味がわからん
例: ルートオブジェクトを単一ブロックに脱出させるとき
scanポインタとfreeポインタの間が1ブロック以上離れないと仕事がグローバルプールへ輸出されない
例: 線形リスト？
スロットをたどることでscanポインタとfreeポインタが進むサイズが同じ
解決策
次の3条件を満たすときにブロックを随時輸出する
プールの大きさが閾値を下回っている
プール: 上で言うscanlistのこと？
コピー先のブロックに輸出する価値があるだけの仕事がある
灰色オブジェクトが多めに詰まっている
ベンチマークによると基準は128ワード、つまり半分以上
走査対象ブロックに走査していないスロットが十分に残っている
走査し始めたばかりで、まだまだブロック境界に到達しそうにない
問題点
コピー先ブロックが完全に空のときに断片化が激しい
走査対象オブジェクトが基準(128ワード)以上のサイズの場合とか？
解決策
空のブロックをできるだけ取らないようにする
Marlowら曰く、この処置による断片化は小さい
Cheney方式の局所性
Cheney方式は幅優先探索なのでミューテータの局所性が下がる(cf. 4.2節, p59)
https://gyazo.com/b3c998b322f5c4ecd7b3aeacbe14fd60
深さ優先探索は局所性があがるが補助スタックが必要
階層的コピーアルゴリズム、階層的分解コレクタ(Moon$ [1984] , Wilson et al.$ [1991] )
ほとんど深さ優先だがスタックがいらない
逐次的アルゴリズム
Siegwart and Hirzel$ [2006]
Imai and Tickの並列コピーコレクタに階層的分解法を加える
scanポインタとfreeポインタの組をうまく使って、並列アルゴリズムでオブジェクトのグラフを階層的に探索する
逐次的な階層的分解コレクタ(Wilson et al.$ [1991] )
途中まで走査されたブロックはscanポインタとfreeポインタの2つをもつ
Imai and Tick
ブロック毎にscanポインタとfreeポインタの組をもつ
コピー先と走査対象が同じブロックになる(aliased)ことを優先する
aliasedにできるかどうかを灰色のスロットの走査直後に判定
これによりオブジェクトグラフの探索が階層的分解法の順序になる
状態遷移系がImai and Tickのスーパーセットになっている
ブロックサイズが128キロバイト
Imai and Tickより大きい
各スレッドが走査対象ブロックを1ブロックキャッシュする
グローバルプールに対する獲得競争の軽減
これはImai and Tickでも効いてくる最適化なのかな？
先にキャッシュされたブロックをこれから走査するブロックの共有プールに返却する可能性がある
scanlist -> scan: キャッシュからブロックを取得
scan -> scanlist: ブロックをキャッシュする
階層的分解法の順序は空間局所性を向上
ほとんどの親子が同じページ(4キロバイト)に収まる
TLBミス率やキャッシュミス率を下げる
コレクタが減速してミューテータが高速化
チャネル
解決策その2
問題点(再掲)
他スレッドとの競争は避けられない
オブジェクトのコピー
mutableオブジェクトの複製を防ぐための競争
転送ポインタの書き込み
負荷分散の性能が悪い
仕事やto空間の空きを分け合う仕組みがない
ワークリストをメモリ空間に結びつけるセマンティクス(Oancea et al.$ [2009] )
NUMAでの性能向上を狙ったメモリ中心の設計
プロセッサ間通信のコストが増大するにつれてハードウェアに馴染みやすい
ヒープを32キロバイト区画に分割
区画数がプロセッサ数に比べてはるかに多い
粒度は通信コストと負荷分散のトレードオフ
各区画が独立してワークリストをもつ
各ワークリストには区画中の走査する必要があるto空間オブジェクトへの参照が入る
引越し先アドレスをワークリストに入れる
各ワークリストは同時に高々1つのプロセッサが所有
ワークリストの入口と出口をそれぞれ高々1つのプロセッサが所有、では？
Single Reader-Single Writerなんだし
ワークリストに入っているスロットを追跡したとき、
参照先のオブジェクトが同じ区画中のオブジェクトの場合
そのワークリストに加える
参照先のオブジェクトが他の区画中のオブジェクトの場合
その区画のワークリストに送る
Single Reader-Single Writerチャネルを使って仕事を交換する
固定長リングバッファで実装(cf. アルゴリズム13-34, p320)
強いメモリ順序が保証される場合はロックやメモリバリアなしでチャネルにスロットを出し入れできる
IntelやAMDのx86
強いメモリ順序が保証されない場合はメモリフェンスなどが必要
PowerPC
不可分操作が必要なのは区画とそのワークリストを取得するときのみ
コレクタスレッドの終了条件
どの区画のワークリストも仕事を所有していない
そのスレッドのすべての入出力チャネルが空
すべてのスレッドのすべてのワークリストが空
スレッドごとにワークリストがある？
終了時にどのスレッドからでも見えるフラグを立てる
開始フェーズでは通常の並列追跡アルゴリズムで処理
副産物の灰色オブジェクトを区画のロックを取りながらそれぞれのワークリストに入れる
ワークリストをプロセッサに割り振って上述のチャネルベースアルゴリズムに移る
カードテーブル
解決策その3
世代別コレクタの年少世代の管理には並列コピー方式がよく用いられる
リメンバードセットの主な実装
リンクリストでつながればバッファ
ブロック構造のアルゴリズムと同様に負荷分散できる
ハッシュテーブル
これまでに述べた何らかの方法で負荷分散できる？
カードテーブル
効果的な負荷分散が難しい
カードテーブル中のマークされたカードに対応するヒープ領域を走査して、世代をまたがる参照を探す
カード走査を並列化する自明なアプローチ
ヒープを等分してプロセッサに静的に割り当てる
コレクタスレッドが競争する
生きているオブジェクトはブロックに偏在する
高密度なブロックの走査に時間の大半が費やされる
解決策
カードテーブルをN個のストライドに分割
各ストライドにはカード番号をNで割った余りが同じものが属する
Nは多分スレッド数？
高密度領域がストライドをまたがって分散する
スレッドがストライドの取得を巡って競争する